import com.sun.javafx.iio.gif.GIFImageLoaderFactory;

/**
 * Created by cc
 * Description:
 * User: CZH
 * Date: 2022-09-25
 * Time: 11:42
 */
class ListNode{
    public int val; //链表的值
    public ListNode next;   //链表下一节点的地址

    public ListNode(int val) {
        this.val = val;
    }
}

public class MyLinkedList {
    //单链表的头节点
    public ListNode head;

    //穷举法 创建链表
    public void createList() {
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(9);
        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(8);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }

    //打印链表
    public void show() {
        //定义一个cur节点记录头节点
        ListNode cur = this.head;
        //只要cur节点不为null
        while (cur != null) {
            //就一直打印节点
            System.out.print(cur.val + " ");
            //打印完就后移cur节点
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表的长度
    public int size() {
        //判断链表是否有值
        if (this.head == null) {
            return 0;
        }
        //头节点不宜移动，定义cur节点
        ListNode cur = this.head;
        int count = 0;
        //只要cur节点不为空
        while (cur != null) {
            count++;
            //节点cur后移
            cur = cur.next;
        }
        return count;
    }

    //查找链表是否包含关键字key
    public boolean contains(int key) {
        //判断链表是否有值
        if (this.head == null) {
            return false;
        }
        //头节点不宜移动，定义cur节点代替
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //添加节点 - 头插法
    public void addFirst(int data) {
        //新建节点
        ListNode node = new ListNode(data);
        //判断是否第一次插入数据
        if (this.head == null) {
            //直接指向即可
            this.head = node;
        }else {
            //新节点的下一节点next 指向现在链表的头节点
            node.next = this.head;
            //更新头节点
            this.head = node;
        }
    }

    //添加节点-尾插法
    public void addLast(int data) {
        //新建节点
        ListNode node = new ListNode(data);
        //头节点为空，直接指向新节点
        if (this.head == null) {
            this.head = node;
        }else {
            //cur代替头节点后移到末尾
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            //把末尾节点的next指向新节点即可
            cur.next = node;
        }
    }

    //通过下标index找到指定数据的前驱节点
    public ListNode searchPrev(int index) {
        // 定义cur代替头节点
        ListNode cur = this.head;
        // 遍历次数比链表长度少一
        // 就可以找到index位置的前驱
        for (int i = 0; i < index-1; i++) {
            cur = cur.next;
        }
        return cur;
    }

    //任意位置插入数据
    public void addIndex(int index, int data) {
        //判断index位置是否合法
        if (index < 0 || index > size()) {
            System.out.println("index有问题");
            return;
        }
        //头插法
        if (index == 0) {
            addFirst(data);
            return;
        }
        //尾插法
        if (index == size()) {
            addLast(data);
            return;
        }
        //中间插入数据
        ListNode prev = searchPrev(index);
        ListNode node = new ListNode(data);
        // 先让前驱节点的next指向node的next
        node.next = prev.next;
        prev.next = node;
    }

    //通过key值，找到关键字为key的节点的前驱
    public ListNode searchPrevNode(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //判断链表是否为空
        if (this.head == null) {
            System.out.println("链表空~");
            return;
        }
        //判断是否有该节点
        if (!contains(key)){
            System.out.println("没有key为" + key + "的节点");
            return;
        }
        //删除的节点是头节点
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        //前驱节点
        ListNode prev = searchPrevNode(key);
        ListNode cur = prev.next;
        //删除的节点在尾巴
        prev.next = cur.next;
        //删除的节点在中间
        if (cur.next != null) {
            cur.next = null;
        }
    }


    //方法一：删除所有值为key的节点
    public void removeAllKey1(int key) {
        if (this.head == null) {
            System.out.println("头节点为空");
            return;
        }
        if (!contains(key)) {
            System.out.println("链表中没有" + key);
            return;
        }

        while (contains(key)) {
            //判断头节点
            if (key == this.head.val) {
                this.head = this.head.next;
                continue;
            }
            //尾节点删除
            ListNode prev = searchPrevNode(key);
            ListNode cur = prev.next;
            prev.next = cur.next;
            if (cur.next != null) {
                cur.next = null;
            }
        }
    }

    //方法二：删除所有值为key的节点
    public void removeAllKey2(int key) {
        //判断链表是否空
        if (this.head == null) {
            System.out.println("链表空");
            return;
        }
        //判断key是否存在
        if (!contains(key)) {
            System.out.println("key不存在");
            return;
        }
        //使用前后指针prev和cur删除
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        //遍历链表判断是否需要删除
        while (cur != null) {
            if (key == cur.val) {
                prev.next = cur.next;
                cur.next = null;
                cur = prev.next;
            }else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        //单独判断头节点
        if (this.head.val == key) {
            this.head = this.head.next;
        }
    }

    //清除链表
    public void clear() {
        //定义一个清理指向的节点cur
        ListNode cur = null;
        //只要头节点非空就清理
        while (this.head != null) {
            //找到头节点位置
            cur = this.head;
            //让头节点先润
            this.head = this.head.next;
            //置空
            cur.next = null;
        }
    }

    //删除所有值为 key 的节点
    public void removeAllKey(int key) {
        if (this.head == null) {
            System.out.println("链表为空");
            return;
        }

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }

        if (this.head.val == key) {
            this.head = this.head.next;
        }
    }



    //反转一个单链表
    public ListNode reverseList() {
        if (this.head == null || this.head.next == null) {
            return this.head;
        }
        ListNode cur = this.head;
        ListNode newHead = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        this.head = newHead;
        return this.head;
    }

    //从newHead处开始打印链表
    public void show2(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //找到链表中的中间结点
    public ListNode findMiddleNode(){
        if (this.head == null || this.head.next == null) {
            return this.head;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //输入一个链表，输出该链表中倒数第k个结点
    public ListNode findLastKey(int k) {
        if (k <= 0 || k > size()) {
            System.out.println("k有问题");
            return null;
        }
        if (this.head == null) {
            System.out.println("空表");
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (k > 0) {
            k--;
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    //将两个有序链表合并为一个新的有序链表并返回。
    //新链表是通过拼接给定的两个链表的所有节点组成的。
    public MyLinkedList mergeTwoLists(MyLinkedList List1) {
        if (List1.head == null && this.head == null) return null;
        if (List1.head == null) return this;
        if (this.head == null) return List1;

        ListNode headA = List1.head;
        ListNode headB = this.head;

        ListNode newHead = null;

        boolean isFlag = true;

        if (headA.val < headB.val) {
            newHead = headA;
            headA = headA.next;
            isFlag = true;
        }else {
            newHead = headB;
            headB = headB.next;
            isFlag = false;
        }

        ListNode cur = newHead;
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                cur.next = headA;
                headA = headA.next;
            }else {
                cur.next = headB;
                headB = headB.next;
            }
            cur = cur.next;
        }

        if (headA == null) cur.next = headB;
        if (headB == null) cur.next = headA;

        if (isFlag == true) {
            return List1;
        }else {
            return this;
        }
    }


    //编写代码，以给定值x为基准将链表分割成两部分，
    // 所有小于x的结点排在大于或等于x的结点之前.
    public ListNode partition(int x) {
        if (this.head == null) {
            return null;
        }
        ListNode cur = this.head;
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;

        while (cur != null) {
            if (cur.val < x) {
                //第一次赋值
                if (as == null) {
                    as = cur;
                    ae = cur;
                }else {
                    //不是第一次赋值
                    ae.next = cur;
                    ae = cur;   //
                }
            }else {
                //第一次赋值
                if (bs == null) {
                    bs = cur;
                    be = cur;

                }else {
                    //不是第一次赋值
                    be.next = cur;
                    be = cur;
//                    be = be.next;
                }
            }
            cur = cur.next;
        }
        //前段as为空
        if (as == null) {
            return bs;
        }
//        ae.next = bs;
//        if (bs != null) {
//            be.next = null;
//        }
//        return as;

        //后段bs为空
        if (bs == null) {
            ae.next = null;
            return as;
        }
        //都有数据，两段连起来
        ae.next = bs;
        //结尾不要忘记置为空
        be.next = null;
        return as;
    }

    //在一个排序的链表中，存在重复的结点，
    // 请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
    public ListNode deleteDuplication(){
        if (this.head == null) return null;

        ListNode newHead = new ListNode(-1);
        ListNode cur = this.head;
        ListNode tmp = newHead;

        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next; //多走一步，渡过最后一个重复节点
            }else {
                tmp.next = cur;
                cur = cur.next;
                tmp = tmp.next;
            }
        }

        tmp.next = null;
        return newHead.next;
    }




    //回文链表
    public boolean chkPalindrome() {
        if (this.head == null) {
            return true;
        }
        if (this.head.next == null) {
            return true;
        }
        //1.找中间节点
        ListNode slow = this.head;
        ListNode fast = this.head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //2.进行反转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //3.前后对比
        while (this.head != slow) {
            if (this.head.val != slow.val) {
                return false;
            }
            //偶数情况
            if (this.head.next == slow) {
                return true;
            }
            this.head = this.head.next;
            slow = slow.next;
        }
        return true;
    }

    //创建有环链表
    public void createCycle(){
        ListNode cur = this.head;
        //需要用到cur.next
        while (cur.next != null) {
            cur = cur.next;
        }
        //判断到最后，直接给它连接上前面的节点
        cur.next = this.head.next;
    }

    //判断链表是否有环
    public boolean hasCycle() {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }


    //判断环形链表的入环节点
    public ListNode detectCycle(){
        //1.让快慢节点按2：1的速度比例移动，直到相遇。
        ListNode fast = this.head;
        ListNode slow = this.head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }

        //防止不是环形链表
        if (fast == null || fast.next == null) {
            return null;
        }

        //2.相遇后，让slow节点回到this.head。
        slow = this.head;

        //3.再次一起移动，按照1：1速度移动，再次相遇就是入环节点。
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }








}
